#include <bits/stdc++.h>

using namespace std;

template<const int _n,const int _m>
struct Edge
{
	struct Edge_base { int to,next; }e[_m]; int cnt,p[_n];
	Edge() { clear(); } void clear() { cnt=0,memset(p,0,sizeof(p)); }
	void insert(const int x,const int y)
	{ e[++cnt].to=y; e[cnt].next=p[x]; p[x]=cnt; return ; }
	int start(const int x) { return p[x]; }
	Edge_base& operator[](const int x) { return e[x]; }
};

struct node
{
	int	val,key,size,cnt;
	node	*l,*r;
	node() {}
	node(const int x) { val=x;key=rand();size=1,cnt=1; l=r=0; }
}U[2000000],*ALL=U,*Trash[2000000];int top=0;

node*	ALLOC(const int x) { return new(top?Trash[top--]:++ALL)node(x); }
void	RECYCLE(node * t) { Trash[++top]=t; }

struct Treap
{
	node	*root;
	Treap() { root=0; }

	void	update(node *& t)
	{ t->size=t->cnt+(t->l?t->l->size:0)+(t->r?t->r->size:0); }
	void	lturn(node *& t)
	{ node * temp=t; t=t->r; temp->r=t->l; t->l=temp; update(t->l); update(t); }
	void	rturn(node *& t)
	{ node * temp=t; t=t->l; temp->l=t->r; t->r=temp; update(t->r); update(t); }

	void	Insert(node *& t,const int d)
	{
		if(!t) { t=ALLOC(d); return ; }
		t->size++; if(t->val==d)t->cnt++;
		else if(d>t->val)
		{
			Insert(t->r,d);
			if(t->r->key<t->key)lturn(t);
		}
		else
		{
			Insert(t->l,d);
			if(t->l->key<t->key)rturn(t);
		}
		return ;
	}

	void	Erase(node *& t,const int d)
	{
		if(!t)return ;
		if(t->val==d)
		{
			if(t->cnt>1) { t->cnt--,t->size--; return ; }
			if(!t->l || !t->r)
			{ node *temp=t; t=(t->l?t->l:(t->r?t->r:0)); RECYCLE(temp); }
			else if(t->l->key<t->r->key)rturn(t),Erase(t,d);
			else	lturn(t),Erase(t,d);
		}
		else if(d>t->val)t->size--,Erase(t->r,d);
		else	t->size--,Erase(t->l,d); return ;
	}

	void	get_pos(node *& t,const int d,int & Ans)
	{
		if(!t)return ; if(t->val==d) { Ans+=(t->r?t->r->size:0); return ; }
		else if(d<t->val) { Ans+=(t->r?t->r->size:0)+t->cnt; get_pos(t->l,d,Ans); }
		else { get_pos(t->r,d,Ans); } return ;
	}

	void	insert(const int d) { Insert(root,d); }
	void	erase(const int d) { Erase(root,d); }
	int	get_pos(const int d) { int Ans=0; get_pos(root,d,Ans); return Ans; }

	void	dfs_print(node * t)
	{
		if(t->l)printf("%d\t\t--L->\t\t%d\n",t->val,t->l->val),dfs_print(t->l);
		if(t->r)printf("%d\t\t--R->\t\t%d\n",t->val,t->r->val),dfs_print(t->r);
	}
	void	print() { printf("***************************************\n"); dfs_print(root); }
}St[263000];

int	n,m,ind,a[81000],pos[81000];
int	hv[81000],Head[81000],Pre[81000],Dfn[81000];
Edge<81000,170000>e;

int	Init_Dfs(const int S,const int fa)
{
	int	s=1,Max=0;
	for(int i=e.start(S);i;i=e[i].next)
	{
		if(e[i].to==fa)continue;
		int	temp=Init_Dfs(e[i].to,S);
		if(temp>Max)Max=temp,hv[S]=e[i].to;
		s+=temp;
	} return s;
}

void	Dfs(const int S,const int fa)
{
	if(!Head[S])Head[S]=Head[fa]; Dfn[S]=++ind;
	if(hv[S])Dfs(hv[S],S);
	for(int i=e.start(S);i;i=e[i].next)
	{
		if(e[i].to==hv[S] || e[i].to==fa)continue;
		Head[e[i].to]=e[i].to;
		Pre[e[i].to]=S;
		Dfs(e[i].to,S);
	} return ;
}

void	Change(const int l,const int r,const int num,
		const int s,const int t,const int d)
{
	if(l==r) { St[num].erase(t); St[num].insert(d); return ; }
	int	mid=l+((r-l)>>1);
	if(s<=mid)Change(l,mid,num<<1,s,t,d);
	if(s>mid)Change(mid+1,r,num<<1|1,s,t,d);
	St[num].erase(t); St[num].insert(d);
	return ;
}

void	Change(const int x,const int y)
{ int temp=a[x];a[x]=y; Change(1,n,1,Dfn[x],temp,y); return ; }

void	Query(const int l,const int r,const int num,const int s,const int t,vector<int>& vec)
{
	if(s<=l && r<=t) { vec.push_back(num); return ; }
	int	mid=l+((r-l)>>1);
	if(t<=mid)return Query(l,mid,num<<1,s,t,vec);
	if(s>mid)return Query(mid+1,r,num<<1|1,s,t,vec);
	return Query(l,mid,num<<1,s,t,vec),Query(mid+1,r,num<<1|1,s,t,vec);
}

void	Jump_Query(int x,int y,vector<int>& vec)
{
	while(Head[x]!=Head[y])
	{
		if(Dfn[Head[x]]>Dfn[Head[y]])
		{
			Query(1,n,1,Dfn[Head[x]],Dfn[x],vec);
			x=Pre[Head[x]];
		}
		else
		{
			Query(1,n,1,Dfn[Head[y]],Dfn[y],vec);
			y=Pre[Head[y]];
		}
	}
	if(Dfn[x]>Dfn[y])Query(1,n,1,Dfn[y],Dfn[x],vec);
	else	Query(1,n,1,Dfn[x],Dfn[y],vec);
	return ;
}

void	Get_size(int x,int y,int & cnt)
{
	while(Head[x]!=Head[y])
	{
		if(Dfn[Head[x]]>Dfn[Head[y]])
		{
			cnt+=Dfn[x]-Dfn[Head[x]]+1;
			x=Pre[Head[x]];
		}
		else
		{
			cnt+=Dfn[y]-Dfn[Head[y]]+1;
			y=Pre[Head[y]];
		}
	}
	if(Dfn[x]>Dfn[y])cnt+=Dfn[x]-Dfn[y]+1;
	else	cnt+=Dfn[y]-Dfn[x]+1;
	return ;
}

int	Query(const vector<int>& vec,const int d)
{
	int	temp=0;
	for(int i=0;i<(int)vec.size();++i)temp+=St[vec[i]].get_pos(d);
	return temp+1;
}

vector<int>	vec;

int	Query(const int x,const int y,const int k)
{
	int	l=-1,r=1e8+1,cnt=0;
	vec.clear();
	Get_size(x,y,cnt);if(cnt<k)return -1;
	Jump_Query(x,y,vec);
	while(l<r-1)
	{
		int	mid=l+((r-l)>>1);
		if(Query(vec,mid)<=k)r=mid;
		else	l=mid;
	}
	return r;
}

void	Build(const int l,const int r,const int num)
{
	if(l==r) { St[num].insert(a[pos[l]]); return ; }
	int	mid=l+((r-l)>>1); Build(l,mid,num<<1); Build(mid+1,r,num<<1|1);
	for(int i=l;i<=r;++i) St[num].insert(a[pos[i]]);
}

int main()
{
	int	i,x,y,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		e.insert(x,y);e.insert(y,x);
	}

	Init_Dfs(1,0); Head[1]=1; Dfs(1,0);
	for(i=1;i<=n;++i)pos[Dfn[i]]=i;
	Build(1,n,1);
	while(m--)
	{
		scanf("%d%d%d",&k,&x,&y);
		if(k==0) Change(x,y);
		else { int	temp=Query(x,y,k); if(temp==-1)printf("invalid request!\n");
			else	printf("%d\n",temp); }
	}
	return 0;
}
